# Heap implementation is much cuter using a Proc object instead of an
# abstract method
class Heap
  # Constructor for custom heaps; pass the Proc object for comparing
  # two keys
  def initialize(&is_top)
    @values = []
    @is_top = is_top
  end

  def Heap.new_max_heap()
    Heap.new() {|val0, val1| val0 > val1 }
  end

  def Heap.new_min_heap()
    Heap.new() {|val0, val1| val0 < val1 }
  end

  def insert(value)
    @values << value
    bubble(value, @values.size - 1)
  end
  
  def top
    @values.first				                  # no idx_out_bounds
  end
  
  def extract_top
    value = @values.delete_at(0)        # no idx_out_bounds
    
    if not @values.empty?
      @values.insert(0, @values.pop())
      hippy_fy(0)
    end
    
    value
  end
  
  def top_up_key(position, value)
    old_value = @values[position]

    raise RuntimeError.new("Not topping up!") if not @is_top.call(value, old_value)
  
    @values[position] = value
    bubble(value, position);
  end
  
  def size()
    @values.size()
  end
  
  protected
  
  def bubble(value, position)
    while position > 0
      pos_parent = (position - 1) / 2
      parent = @values[pos_parent]
      
      # stop when the parent is top
      break if @is_top.call(parent, value)
      
      @values[position], @values[pos_parent] = @values[pos_parent], @values[position]
      position = pos_parent 
    end
  end

  # :-))))
  def hippy_fy(position)
    pos_largest = position
    value = @values[position]
    
    pos_left = 2 * position + 1
    has_left = pos_left < @values.size
    
    if has_left
      left = @values[pos_left]
      pos_largest = pos_left if @is_top.call(left, value)
    end
    
    pos_right = 2 * position + 2
    has_right = pos_right < @values.size
    
    if has_right
      right = @values[pos_right]
      largest = @values[pos_largest]
      pos_largest = pos_right if @is_top.call(right, largest)
    end

    if pos_largest != position
      @values[position], @values[pos_largest] = @values[pos_largest], @values[position]
      hippy_fy(pos_largest)  
    end
  end
end